/**组合算法*/

#include <iostream>
#include <algorithm>

#define left 0
#define right 1
#define MAX_INT 1<<30
using namespace std;
/**输出所有排列*/
void genAllPermute(int n)
{
    int num[n+2];
    int direct[n+2];
    for(int i=1;i<=n;++i){
        num[i]=i;
        direct[i]=left;
    }
    num[0]=num[n+1]=MAX_INT;
    for(;;){
        /*
        for(int i=1;i<=n;++i)
            cout<<num[i];
        cout<<endl;
        */
        int maxMobile = -1;
        int maxIndex = 0;
        for(int i=1;i<=n;++i){
            //if(num[i]>maxMobile && ((direct[i]==left && num[i-1]<num[i])||(direct[i]==right && num[i+1]<num[i]))
            if(direct[i] == left){
                if(num[i-1]<num[i] && num[i]>maxMobile){
                    maxMobile = num[i];
                    maxIndex = i;
                }
            } else{
                if(num[i+1]<num[i] && num[i]>maxMobile){
                    maxMobile = num[i];
                    maxIndex = i;
                }
            }
        }
        if(maxMobile == -1)
            break;
        if(direct[maxIndex] == left){
            swap(direct[maxIndex], direct[maxIndex-1]);
            swap(num[maxIndex], num[maxIndex-1]);
        }else{
            swap(direct[maxIndex], direct[maxIndex+1]);
            swap(num[maxIndex], num[maxIndex+1]);
        }
        for(int i=1;i<=n;++i){
            if(num[i]>maxMobile){
                direct[i] ^= 1;//反向
            }
        }
    }
}
static void perm(int list[],int s, int t)
{
    if(s == t){
        /*
        for (int i=0;i<=t;++i)cout<<list[i];
        cout<<endl;
        */
    }else{
        for (int i=s;i<=t;++i){
            swap(list[s],list[i]);
            perm(list,s+1,t);
            swap(list[s],list[i]);
        }
    }
}
void genAllPermuteRecursive(int n)
{
    int list[n];
    for(int i=0;i<n;++i)list[i]=i+1;
    perm(list,0,n-1);
}
#include <ctime>
#include <cstdio>
void compareTwoPermuteAlgo()
{
    int n = 11;
    clock_t start;
    long t;
    double nans;
    start = clock();

    genAllPermute(n);
    t = clock()-start;
    nans = t *1.0/ CLOCKS_PER_SEC;
	printf("%8.2f\n", nans);


    start = clock();
    genAllPermuteRecursive(n);
    t = clock()-start;
    nans = t *1.0/ CLOCKS_PER_SEC;
	printf("%8.2f\n", nans);
}
int main()
{
    compareTwoPermuteAlgo();
}
